home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / dict / dic_impl.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  4KB  |  199 lines
  1. #include <LEDA/dictionary.h>
  2.  
  3. /* a simple dictionary implementation by doubly linked lists */
  4.  
  5.  
  6. #include <LEDA/list.h>
  7.  
  8. class list_dic_pair
  9. {
  10.   friend class dic_impl;
  11.  
  12.   GenPtr key;
  13.   GenPtr inf;
  14.  
  15.   public:
  16.   list_dic_pair(GenPtr k=0, GenPtr i=0) { key = k;  inf = i; }
  17.   list_dic_pair(const list_dic_pair& p) { key = p.key; inf = p.inf; }
  18.  
  19.   LEDA_MEMORY(list_dic_pair)
  20. };
  21.  
  22.  
  23. // we define dummy I/O and compare routines
  24.  
  25. void Print(const list_dic_pair&, ostream&)  {}
  26. void Read(list_dic_pair&,istream&) {}
  27. int  compare(const list_dic_pair&,const list_dic_pair&) { return 0; }
  28.  
  29.  
  30. #if !defined(__TEMPLATE_FUNCTIONS__)
  31. LEDA_TYPE_PARAMETER(list_dic_pair)
  32. #endif
  33.  
  34.  
  35. class dic_impl {
  36.  
  37. private:
  38.  
  39. virtual int  cmp(GenPtr, GenPtr) const = 0;
  40. virtual void clear_key(GenPtr&)  const = 0;
  41. virtual void clear_inf(GenPtr&)  const = 0;
  42. virtual void copy_key(GenPtr&)   const = 0;
  43. virtual void copy_inf(GenPtr&)   const = 0;
  44.  
  45.  
  46. /* simple example implementation by a doubly linked list */
  47.  
  48. list<list_dic_pair> L;
  49.  
  50. public:
  51.  
  52.  dic_impl();
  53.  dic_impl(const dic_impl&);
  54.  virtual ~dic_impl();
  55.  
  56. dic_impl& operator=(const dic_impl&);
  57.  
  58. GenPtr key(list_item p)  const;
  59. GenPtr inf(list_item p)  const;
  60.  
  61. list_item item(GenPtr) const;
  62.  
  63. list_item insert(GenPtr,GenPtr);
  64. list_item lookup(GenPtr)  const;
  65. list_item first_item() const;
  66. list_item next_item(list_item) const;
  67.  
  68. void    change_inf(list_item,GenPtr);
  69. void    del_item(list_item);
  70. void    del(GenPtr);
  71. void    clear();
  72.  
  73. int     size()        const;
  74.  
  75. };
  76.  
  77.  
  78.  
  79. inline dic_impl::dic_impl()  {}
  80. inline dic_impl::~dic_impl() { clear(); }
  81.  
  82. inline int    dic_impl::size() const            { return L.size(); }
  83. inline GenPtr dic_impl::key(list_item i)  const { return L[i].key; }
  84. inline GenPtr dic_impl::inf(list_item i)  const { return L[i].inf; }
  85.  
  86. inline list_item dic_impl::item(GenPtr p) const { return list_item(p); }
  87. inline list_item dic_impl::first_item()   const { return L.first(); }
  88. inline list_item dic_impl::next_item(list_item i) const 
  89.                                                 { return L.next_item(i); }
  90.  
  91.  
  92. dic_impl::dic_impl(const dic_impl& D) 
  93. { list_item i;
  94.   L = D.L;
  95.   forall_items(i,L) 
  96.   { D.copy_key(L[i].key);
  97.     D.copy_inf(L[i].inf);
  98.    }
  99.  }
  100.  
  101.  
  102. dic_impl& dic_impl::operator=(const dic_impl& D)
  103. { if (this == &D) return *this;
  104.   clear(); 
  105.   L = D.L;
  106.   list_item i;
  107.   forall_items(i,L) 
  108.   { D.copy_key(L[i].key);
  109.     D.copy_inf(L[i].inf);
  110.    }
  111.   return *this;
  112.  }
  113.  
  114.  
  115. list_item  dic_impl::insert(GenPtr key, GenPtr inf) 
  116. {  list_item i = lookup(key);
  117.    if (i != nil)
  118.      { clear_inf(L[i].inf);
  119.        copy_inf(inf);
  120.        L[i].inf = inf;
  121.        return i;
  122.       }
  123.    else
  124.      { copy_key(key);
  125.        copy_inf(inf);
  126.        return L.push(list_dic_pair(key,inf));
  127.       }
  128. }
  129.  
  130.  
  131. list_item  dic_impl::lookup(GenPtr key)  const
  132. { for(list_item i = L.first(); i; i = L.succ(i))
  133.     if (L[i].key == key) break;
  134.   return i;
  135.  }
  136.  
  137.  
  138. void    dic_impl::change_inf(list_item i, GenPtr inf)
  139. { clear_inf(L[i].inf);
  140.   copy_inf(inf);
  141.   L[i].inf = inf;
  142.  }
  143.  
  144. void    dic_impl::del_item(list_item i)
  145. { clear_key(L[i].key);
  146.   clear_inf(L[i].inf);
  147.   L.del(i);
  148. }
  149.  
  150. void    dic_impl::del(GenPtr key)
  151. { list_item i = lookup(key);
  152.   if (i!=nil) del_item(i);
  153.  }
  154.  
  155. void    dic_impl::clear() 
  156. { list_item i;
  157.   forall_items(i,L)
  158.   { clear_key(L[i].key);
  159.     clear_inf(L[i].inf);
  160.    }
  161.   L.clear();
  162.  }
  163.  
  164.  
  165.  
  166.  
  167.  
  168. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  169. declare3(_dictionary,int,int,dic_impl)
  170. #endif
  171.  
  172.  
  173. main() 
  174. { 
  175. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  176.   _dictionary<int,int,dic_impl> D; 
  177. #else
  178.   _dictionary(int,int,dic_impl) D; 
  179. #endif
  180.  
  181.   dic_item it;
  182.  
  183.   int N = read_int("N = ");
  184.  
  185.   while (N--)
  186.   { int k = random(1,20);
  187.     it = D.lookup(k);
  188.     if (it == nil) 
  189.        D.insert(k,1);
  190.     else
  191.        D.change_inf(it,D.inf(it)+1);
  192.    }
  193.  
  194.   forall_items(it,D) 
  195.      cout << string("%3d  # = %2d\n",D.key(it),D.inf(it));
  196.  
  197.  }
  198.  
  199.